package com.gao.alg.geek;

/**
 * 移动零：
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 */
public class MoveZeros {


    /**
     * 遍历数组
     * 遇到为0的计数
     * 遇到不为0的，向前移动j个位置
     * 最后j个元素赋值0
     * @param nums
     */
    public void moveZeroes1(int[] nums) {

//        int j = 0;
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i]==0){
//                j++;
//            }else {
//                nums[i-j] = nums[i];
//            }
//        }
//        for (int i = 0; i < j; i++) {
//            nums[nums.length-1-i] =0;
//        }
//      优化写法，少一次遍历
        int n=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0){
                n++;
            }else {
                if (n>0){
                    nums[i-n] = nums[i];
                    nums[i] = 0;
                }
            }
        }
    }

    /**
     *遍历数组
     * 使用指针k，指针k的左边都非0
     * 遇到非0，赋值到当前k位置
     * 数组遍历指针i不等于k的时候，说明有0元素，i位置元素赋值0
     * 指针k向右移动
     * @param nums
     */
    public void moveZeroes2(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                nums[k] = nums[i];
                if (i != k){
                    nums[i] = 0;
                }
                k++;
            }
        }
    }

    /**
     * 交换法
     *指针k的左边都是非零
     * @param nums
     */
    public void moveZeroes3(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                int temp = nums[i];
                nums[i] = nums[k];
                nums[k] =  temp;
                k++;
            }
        }
    }
}
